package com.arithmetic.basics;
/*举个例子
比如 n = 4：
f[0] = 1
f[1] = 1
f[2] = f[1] + f[0] = 1 + 1 = 2 (两种方法：1+1 或 2)
f[3] = f[2] + f[1] = 2 + 1 = 3 (三种方法：1+1+1, 1+2, 2+1)
f[4] = f[3] + f[2] = 3 + 2 = 5 (五种方法)
这就是典型的斐波那契数列问题*/
public class Day25 {

    public static void main(String[] args) {
        System.out.println(climbStairs(4));
    }

    public static int climbStairs(int n) {
        // 计算爬n阶台阶的方法数，每次可爬1或2阶
        // 若n=1，直接返回1
        // 创建数组f，f[i]表示第i阶台阶的方法数
        // 初始化f[0] = 1,f[1] = 1
        // 从2到n，从f[i-1]和f[i-2]求和，得到f[i]
        // 返回f[n]
        if (n == 1) { // 若一次爬1阶台阶，方法数是1
            return 1;
        }
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}
